class Solution {
    /**
        可以用Deque获取每层的首尾节点
    
     */
    public int widthOfBinaryTree(TreeNode root) {
        if(root==null)
            return 0;
        Queue<TreeNode> q = new LinkedList<>();
        root.val = 1;
        q.add(root);
        int ans = 1;
        while (q.size()>0){
            int len = q.size();
            int minVal = Integer.MAX_VALUE;
            int maxVal = Integer.MIN_VALUE;
            for (int i = 0; i < len; i++) {
                TreeNode top = q.poll();
                minVal = Math.min(minVal,top.val);
                maxVal = Math.max(maxVal,top.val);
                if(top.left!=null ){
                    top.left.val = top.val <<1;
                    q.add(top.left);
                }
                if(top.right!=null){
                    top.right.val = (top.val<<1)+1;
                    q.add(top.right);
                }
            }
            ans = Math.max(ans,maxVal-minVal+1);
        }

        return ans;
    }
}